# 玩具蛇
# Date: 2025/3/27


def toy_snake():
    res = set()

    def backtrack(path, r, c):
        """
        参数:
            r和c表示当前蛇尾的坐标
            path表示目前蛇身的路径, path[0]为蛇头的位置
        """
        nonlocal res
        path.append((r, c))
        if len(path) == 16:
            res.add(str(path[:]))
            return

        if r + 1 <= 3 and (r + 1, c) not in path:
            backtrack(path, r + 1, c)
            path.pop()
        if r - 1 >= 0 and (r - 1, c) not in path:
            backtrack(path, r - 1, c)
            path.pop()
        if c + 1 <= 3 and (r, c + 1) not in path:
            backtrack(path, r, c + 1)
            path.pop()
        if c - 1 >= 0 and (r, c - 1) not in path:
            backtrack(path, r, c - 1)
            path.pop()

    # 蛇头放置在左上角即可, 因为坐标左右对称, 最后的结果乘以4即可
    for i in range(2):
        for j in range(2):
            backtrack([], i, j)
    return len(res) * 4


if __name__ == '__main__':
    print(toy_snake())  # 552
